#include <stdio.h>
#include <stdlib.h>
#include <string.h>


#define ASIZE 256

void preBmBc(char *x, int m, int bmBc[])
{
    int i;
    for (i = 0; i < ASIZE; ++i)
        bmBc[i] = m;
    for (i = 0; i < m - 1; ++i)
        bmBc[x[i]] = m - i - 1;
}

long int HORSPOOL(char *x, int m, char *y, int n)
{
    int j, bmBc[ASIZE];
    char c;
    long int count = 0;

    preBmBc(x, m, bmBc);

    j = 0;
    while (j <= n - m) {
        c = y[j + m - 1];
        if (x[m - 1] == c && memcmp(x, y + j, m - 1) == 0)
            count++;
        j += bmBc[c];
    }
    return count;
}
